package com.atwulidun.sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {9, -8, 7, 6, -5, 4, 3, 2, 1};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //    // 定义一个调整堆的方法
//    /**
//     *
//     * @param arr
//     * 需要被排序的数组
//     * @param i
//     * 当前需要被调整为大顶堆的子二叉树的根结点(非叶子结点)所对应的坐标
//     * @param length
//     * 当前需要被调整为大顶堆的元素的坐标的右边界(取不到)
//     */
//    public static void adjustHeap(int[] arr, int i, int length) {
//        // 定义一个临时变量来保存当前非叶子结点的值
//        int temp = arr[i];
//        // 通过一个for循环来进行调整，从当前非叶子结点的左子结点开始
//        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
//            // 如果左结点的值小于右结点的值，则k指向右结点
//            // 为了保证数组不越界，必须先加k + 1 < length的判断！！！！！！！！！！
//            if (k + 1 < length && arr[k] < arr[k + 1]) {
//                k++;
//            }
//            // 将左右结点的最大值和temp进行比较
//            if (arr[k] > temp) {
//                // 如果左右结点的最大值比temp大，则把arr[k]的值赋给arr[i]
//                arr[i] = arr[k];
//                // 同时把i指向刚赋值的这个k，此时会再进入for循环，以k为根结点的子二叉树可能也要进行一个调整，
//                // temp的值会一直往下沉，直到找到合适的位置
//                i = k;
//            } else {
//                // 拿到一个无序数组来构建大顶堆，首先要找到最后一个非叶子结点，然后按照从右到左，从下到上的顺序
//                // 来调整当前根结点所在的子二叉树为大顶堆，所以在调整当前结点的时候，分别以当前结点的左右结点为
//                // 根结点的子二叉树已经被调整为两个大顶堆了，所以当arr[k] < temp时，只要保持当前结构即可
//                break;
//            }
//        }
//        // 当for循环结束后，temp已经找到了合适的位置了，将其赋值给该位置即可
//        arr[i] = temp;
//    }
//
//    // 定义一个堆排序的方法
//    public static void heapSort(int[] arr) {
//        // 一、首先要将拿到的无序数组arr调整为一个大顶堆
//        // 问题：为什么不直接从arr的根结点开始调整，而是要用以下的方式进行调整？
//        // 答：用以下方式进行调整，可以保证调整在可控的局部范围内进行，以局部有序形成整体有序；
//        // 如果直接从arr根结点开始调整，那么调整就是整体而不可控的，调整次数和难度会大大地增加
//        // 从最后的一个非叶子结点开始，又因为根结点也要调整，故结束条件为i == 0
//        for (int i = arr.length / 2 - 1; i >= 0; i--) {
//            // 在调整的过程当中，可能会涉及到最后的一个结点，因此被调整的元素坐标的右边界为arr.length
//            adjustHeap(arr, i, arr.length);
//        }
//        // 二、大顶堆构建完成，此时需要将有效长度(adjustHeap的第三个入参表示的值)内的第一个值和最后一个值进行交换
//        // 从arr的最后一个元素开始，因为第一个元素不需要跟自己交换，故结束条件为j == 1
//        for (int j = arr.length - 1; j > 0 ; j--) {
//            // 交换有效长度内的第一和最后一个元素，则最大的元素沉到后面
//            int temp = arr[j];
//            arr[j] = arr[0];
//            arr[0] = temp;
//            // 交换完之后需要对arr根结点下新的有效长度内的元素进行一个调整
//            // 能够调用adjustHeap(int[] arr, int i, int length)的前提是i以下的元素已经是符合大顶堆的结构，
//            // 就跟该方法里面能直接break的情况一致
//            adjustHeap(arr, 0, j);// 当j == 1时，该函数里取到的是arr[0]
//        }
//    }
    private static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        // 特别注意：下面的length不能写成arr.length！！！
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            if ((k + 1) < length && arr[k + 1] > arr[k]) {
                k++;
            }
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

    private static void heapSort(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjustHeap(arr, 0, i);
        }
    }
}
